|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
// NOTE: This code is derived from an implementation originally in dotnet/runtime:
// https://github.com/dotnet/runtime/blob/v5.0.2/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs
//
// See the commentary in https://github.com/dotnet/roslyn/pull/50156 for notes on incorporating changes made to the
// reference implementation.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
using Microsoft.CodeAnalysis.Collections.Internal;
namespace Microsoft.CodeAnalysis.Collections
{
/// <summary>
/// Represents a collection of keys and values.
/// </summary>
/// <remarks>
/// <para>This collection has the same performance characteristics as <see cref="Dictionary{TKey, TValue}"/>, but
/// uses segmented arrays to avoid allocations in the Large Object Heap.</para>
/// </remarks>
/// <typeparam name="TKey">The type of the keys in the dictionary.</typeparam>
/// <typeparam name="TValue">The type of the values in the dictionary.</typeparam>
[DebuggerTypeProxy(typeof(IDictionaryDebugView<,>))]
[DebuggerDisplay("Count = {Count}")]
internal sealed class SegmentedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>
where TKey : notnull
{
private const bool SupportsComparerDevirtualization
#if NETCOREAPP
= true;
#else
= false;
#endif
private SegmentedArray<int> _buckets;
private SegmentedArray<Entry> _entries;
private ulong _fastModMultiplier;
private int _count;
private int _freeList;
private int _freeCount;
private int _version;
#if NETCOREAPP
private readonly IEqualityComparer<TKey>? _comparer;
#else
/// <summary>
/// <see cref="EqualityComparer{T}.Default"/> doesn't devirtualize on .NET Framework, so we always ensure
/// <see cref="_comparer"/> is initialized to a non-<see langword="null"/> value.
/// </summary>
private readonly IEqualityComparer<TKey> _comparer;
#endif
private KeyCollection? _keys;
private ValueCollection? _values;
private const int StartOfFreeList = -3;
public SegmentedDictionary()
: this(0, null)
{
}
public SegmentedDictionary(int capacity)
: this(capacity, null)
{
}
public SegmentedDictionary(IEqualityComparer<TKey>? comparer)
: this(0, comparer)
{
}
public SegmentedDictionary(int capacity, IEqualityComparer<TKey>? comparer)
{
if (capacity < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
}
if (capacity > 0)
{
Initialize(capacity);
}
if (comparer != null && comparer != EqualityComparer<TKey>.Default) // first check for null to avoid forcing default comparer instantiation unnecessarily
{
_comparer = comparer;
}
#if !NETCOREAPP
// .NET Framework doesn't support devirtualization, so we always initialize comparer to a non-null value
_comparer ??= EqualityComparer<TKey>.Default;
#endif
}
public SegmentedDictionary(IDictionary<TKey, TValue> dictionary)
: this(dictionary, null)
{
}
public SegmentedDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey>? comparer)
: this(dictionary != null ? dictionary.Count : 0, comparer)
{
if (dictionary == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
}
// It is likely that the passed-in dictionary is SegmentedDictionary<TKey,TValue>. When this is the case,
// avoid the enumerator allocation and overhead by looping through the entries array directly.
// We only do this when dictionary is SegmentedDictionary<TKey,TValue> and not a subclass, to maintain
// back-compat with subclasses that may have overridden the enumerator behavior.
if (dictionary.GetType() == typeof(SegmentedDictionary<TKey, TValue>))
{
var d = (SegmentedDictionary<TKey, TValue>)dictionary;
var count = d._count;
var entries = d._entries;
for (var i = 0; i < count; i++)
{
if (entries[i]._next >= -1)
{
Add(entries[i]._key, entries[i]._value);
}
}
return;
}
foreach (var pair in dictionary)
{
Add(pair.Key, pair.Value);
}
}
public SegmentedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection)
: this(collection, null)
{
}
public SegmentedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey>? comparer)
: this((collection as ICollection<KeyValuePair<TKey, TValue>>)?.Count ?? 0, comparer)
{
if (collection == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
}
foreach (var pair in collection)
{
Add(pair.Key, pair.Value);
}
}
public IEqualityComparer<TKey> Comparer
{
get
{
return _comparer ?? EqualityComparer<TKey>.Default;
}
}
public int Count => _count - _freeCount;
public KeyCollection Keys => _keys ??= new KeyCollection(this);
ICollection<TKey> IDictionary<TKey, TValue>.Keys => Keys;
IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys => Keys;
public ValueCollection Values => _values ??= new ValueCollection(this);
ICollection<TValue> IDictionary<TKey, TValue>.Values => Values;
IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values => Values;
public TValue this[TKey key]
{
get
{
ref var value = ref FindValue(key);
if (!RoslynUnsafe.IsNullRef(ref value))
{
return value;
}
ThrowHelper.ThrowKeyNotFoundException(key);
return default;
}
set
{
var modified = TryInsert(key, value, InsertionBehavior.OverwriteExisting);
Debug.Assert(modified);
}
}
public void Add(TKey key, TValue value)
{
var modified = TryInsert(key, value, InsertionBehavior.ThrowOnExisting);
Debug.Assert(modified); // If there was an existing key and the Add failed, an exception will already have been thrown.
}
void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair)
=> Add(keyValuePair.Key, keyValuePair.Value);
bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair)
{
ref var value = ref FindValue(keyValuePair.Key);
if (!RoslynUnsafe.IsNullRef(ref value) && EqualityComparer<TValue>.Default.Equals(value, keyValuePair.Value))
{
return true;
}
return false;
}
bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair)
{
ref var value = ref FindValue(keyValuePair.Key);
if (!RoslynUnsafe.IsNullRef(ref value) && EqualityComparer<TValue>.Default.Equals(value, keyValuePair.Value))
{
Remove(keyValuePair.Key);
return true;
}
return false;
}
public void Clear()
{
var count = _count;
if (count > 0)
{
Debug.Assert(_buckets.Length > 0, "_buckets should be non-empty");
Debug.Assert(_entries.Length > 0, "_entries should be non-empty");
SegmentedArray.Clear(_buckets, 0, _buckets.Length);
_count = 0;
_freeList = -1;
_freeCount = 0;
SegmentedArray.Clear(_entries, 0, count);
}
}
public bool ContainsKey(TKey key)
=> !RoslynUnsafe.IsNullRef(ref FindValue(key));
public bool ContainsValue(TValue value)
{
var entries = _entries;
if (value == null)
{
for (var i = 0; i < _count; i++)
{
if (entries[i]._next >= -1 && entries[i]._value == null)
{
return true;
}
}
}
else if (SupportsComparerDevirtualization && typeof(TValue).IsValueType)
{
// ValueType: Devirtualize with EqualityComparer<TValue>.Default intrinsic
for (var i = 0; i < _count; i++)
{
if (entries[i]._next >= -1 && EqualityComparer<TValue>.Default.Equals(entries[i]._value, value))
{
return true;
}
}
}
else
{
// Object type: Shared Generic, EqualityComparer<TValue>.Default won't devirtualize
// https://github.com/dotnet/runtime/issues/10050
// So cache in a local rather than get EqualityComparer per loop iteration
var defaultComparer = EqualityComparer<TValue>.Default;
for (var i = 0; i < _count; i++)
{
if (entries[i]._next >= -1 && defaultComparer.Equals(entries[i]._value, value))
{
return true;
}
}
}
return false;
}
private void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if ((uint)index > (uint)array.Length)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (array.Length - index < Count)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
}
var count = _count;
var entries = _entries;
for (var i = 0; i < count; i++)
{
if (entries[i]._next >= -1)
{
array[index++] = new KeyValuePair<TKey, TValue>(entries[i]._key, entries[i]._value);
}
}
}
public Enumerator GetEnumerator()
=> new(this, Enumerator.KeyValuePair);
IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
=> new Enumerator(this, Enumerator.KeyValuePair);
private ref TValue FindValue(TKey key)
{
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
ref var entry = ref RoslynUnsafe.NullRef<Entry>();
if (_buckets.Length > 0)
{
Debug.Assert(_entries.Length > 0, "expected entries to be non-empty");
var comparer = _comparer;
if (SupportsComparerDevirtualization && comparer == null)
{
var hashCode = (uint)key.GetHashCode();
var i = GetBucket(hashCode);
var entries = _entries;
uint collisionCount = 0;
if (typeof(TKey).IsValueType)
{
// ValueType: Devirtualize with EqualityComparer<TValue>.Default intrinsic
i--; // Value in _buckets is 1-based; subtract 1 from i. We do it here so it fuses with the following conditional.
do
{
// Should be a while loop https://github.com/dotnet/runtime/issues/9422
// Test in if to drop range check for following array access
if ((uint)i >= (uint)entries.Length)
{
goto ReturnNotFound;
}
entry = ref entries[i];
if (entry._hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entry._key, key))
{
goto ReturnFound;
}
i = entry._next;
collisionCount++;
} while (collisionCount <= (uint)entries.Length);
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
goto ConcurrentOperation;
}
else
{
// Object type: Shared Generic, EqualityComparer<TValue>.Default won't devirtualize
// https://github.com/dotnet/runtime/issues/10050
// So cache in a local rather than get EqualityComparer per loop iteration
var defaultComparer = EqualityComparer<TKey>.Default;
i--; // Value in _buckets is 1-based; subtract 1 from i. We do it here so it fuses with the following conditional.
do
{
// Should be a while loop https://github.com/dotnet/runtime/issues/9422
// Test in if to drop range check for following array access
if ((uint)i >= (uint)entries.Length)
{
goto ReturnNotFound;
}
entry = ref entries[i];
if (entry._hashCode == hashCode && defaultComparer.Equals(entry._key, key))
{
goto ReturnFound;
}
i = entry._next;
collisionCount++;
} while (collisionCount <= (uint)entries.Length);
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
goto ConcurrentOperation;
}
}
else
{
var hashCode = (uint)comparer.GetHashCode(key);
var i = GetBucket(hashCode);
var entries = _entries;
uint collisionCount = 0;
i--; // Value in _buckets is 1-based; subtract 1 from i. We do it here so it fuses with the following conditional.
do
{
// Should be a while loop https://github.com/dotnet/runtime/issues/9422
// Test in if to drop range check for following array access
if ((uint)i >= (uint)entries.Length)
{
goto ReturnNotFound;
}
entry = ref entries[i];
if (entry._hashCode == hashCode && comparer.Equals(entry._key, key))
{
goto ReturnFound;
}
i = entry._next;
collisionCount++;
} while (collisionCount <= (uint)entries.Length);
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
goto ConcurrentOperation;
}
}
goto ReturnNotFound;
ConcurrentOperation:
ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
ReturnFound:
ref TValue value = ref entry._value;
Return:
return ref value;
ReturnNotFound:
value = ref RoslynUnsafe.NullRef<TValue>();
goto Return;
}
private int Initialize(int capacity)
{
var size = HashHelpers.GetPrime(capacity);
var buckets = new SegmentedArray<int>(size);
var entries = new SegmentedArray<Entry>(size);
// Assign member variables after both arrays allocated to guard against corruption from OOM if second fails
_freeList = -1;
_fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)size);
_buckets = buckets;
_entries = entries;
return size;
}
private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
{
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (_buckets.Length == 0)
{
Initialize(0);
}
Debug.Assert(_buckets.Length > 0);
var entries = _entries;
Debug.Assert(entries.Length > 0, "expected entries to be non-empty");
var comparer = _comparer;
var hashCode = (uint)((SupportsComparerDevirtualization && comparer == null) ? key.GetHashCode() : comparer.GetHashCode(key));
uint collisionCount = 0;
ref var bucket = ref GetBucket(hashCode);
var i = bucket - 1; // Value in _buckets is 1-based
if (SupportsComparerDevirtualization && comparer == null)
{
if (typeof(TKey).IsValueType)
{
// ValueType: Devirtualize with EqualityComparer<TValue>.Default intrinsic
while (true)
{
// Should be a while loop https://github.com/dotnet/runtime/issues/9422
// Test uint in if rather than loop condition to drop range check for following array access
if ((uint)i >= (uint)entries.Length)
{
break;
}
if (entries[i]._hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i]._key, key))
{
if (behavior == InsertionBehavior.OverwriteExisting)
{
entries[i]._value = value;
return true;
}
if (behavior == InsertionBehavior.ThrowOnExisting)
{
ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
}
return false;
}
i = entries[i]._next;
collisionCount++;
if (collisionCount > (uint)entries.Length)
{
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
}
}
}
else
{
// Object type: Shared Generic, EqualityComparer<TValue>.Default won't devirtualize
// https://github.com/dotnet/runtime/issues/10050
// So cache in a local rather than get EqualityComparer per loop iteration
var defaultComparer = EqualityComparer<TKey>.Default;
while (true)
{
// Should be a while loop https://github.com/dotnet/runtime/issues/9422
// Test uint in if rather than loop condition to drop range check for following array access
if ((uint)i >= (uint)entries.Length)
{
break;
}
if (entries[i]._hashCode == hashCode && defaultComparer.Equals(entries[i]._key, key))
{
if (behavior == InsertionBehavior.OverwriteExisting)
{
entries[i]._value = value;
return true;
}
if (behavior == InsertionBehavior.ThrowOnExisting)
{
ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
}
return false;
}
i = entries[i]._next;
collisionCount++;
if (collisionCount > (uint)entries.Length)
{
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
}
}
}
}
else
{
while (true)
{
// Should be a while loop https://github.com/dotnet/runtime/issues/9422
// Test uint in if rather than loop condition to drop range check for following array access
if ((uint)i >= (uint)entries.Length)
{
break;
}
if (entries[i]._hashCode == hashCode && comparer.Equals(entries[i]._key, key))
{
if (behavior == InsertionBehavior.OverwriteExisting)
{
entries[i]._value = value;
return true;
}
if (behavior == InsertionBehavior.ThrowOnExisting)
{
ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
}
return false;
}
i = entries[i]._next;
collisionCount++;
if (collisionCount > (uint)entries.Length)
{
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
}
}
}
int index;
if (_freeCount > 0)
{
index = _freeList;
Debug.Assert((StartOfFreeList - entries[_freeList]._next) >= -1, "shouldn't overflow because `next` cannot underflow");
_freeList = StartOfFreeList - entries[_freeList]._next;
_freeCount--;
}
else
{
var count = _count;
if (count == entries.Length)
{
Resize();
bucket = ref GetBucket(hashCode);
}
index = count;
_count = count + 1;
entries = _entries;
}
ref var entry = ref entries![index];
entry._hashCode = hashCode;
entry._next = bucket - 1; // Value in _buckets is 1-based
entry._key = key;
entry._value = value; // Value in _buckets is 1-based
bucket = index + 1;
_version++;
return true;
}
private void Resize()
=> Resize(HashHelpers.ExpandPrime(_count));
private void Resize(int newSize)
{
Debug.Assert(_entries.Length > 0, "_entries should be non-empty");
Debug.Assert(newSize >= _entries.Length);
var entries = new SegmentedArray<Entry>(newSize);
var count = _count;
SegmentedArray.Copy(_entries, entries, count);
// Assign member variables after both arrays allocated to guard against corruption from OOM if second fails
_buckets = new SegmentedArray<int>(newSize);
_fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)newSize);
for (var i = 0; i < count; i++)
{
if (entries[i]._next >= -1)
{
ref var bucket = ref GetBucket(entries[i]._hashCode);
entries[i]._next = bucket - 1; // Value in _buckets is 1-based
bucket = i + 1;
}
}
_entries = entries;
}
public bool Remove(TKey key)
{
// The overload Remove(TKey key, out TValue value) is a copy of this method with one additional
// statement to copy the value for entry being removed into the output parameter.
// Code has been intentionally duplicated for performance reasons.
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (_buckets.Length > 0)
{
Debug.Assert(_entries.Length > 0, "entries should be non-empty");
uint collisionCount = 0;
var hashCode = (uint)(_comparer?.GetHashCode(key) ?? key.GetHashCode());
ref var bucket = ref GetBucket(hashCode);
var entries = _entries;
var last = -1;
var i = bucket - 1; // Value in buckets is 1-based
while (i >= 0)
{
ref var entry = ref entries[i];
if (entry._hashCode == hashCode && (_comparer?.Equals(entry._key, key) ?? EqualityComparer<TKey>.Default.Equals(entry._key, key)))
{
if (last < 0)
{
bucket = entry._next + 1; // Value in buckets is 1-based
}
else
{
entries[last]._next = entry._next;
}
Debug.Assert((StartOfFreeList - _freeList) < 0, "shouldn't underflow because max hashtable length is MaxPrimeArrayLength = 0x7FEFFFFD(2146435069) _freelist underflow threshold 2147483646");
entry._next = StartOfFreeList - _freeList;
#if NETCOREAPP
if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>())
#endif
{
entry._key = default!;
}
#if NETCOREAPP
if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>())
#endif
{
entry._value = default!;
}
_freeList = i;
_freeCount++;
return true;
}
last = i;
i = entry._next;
collisionCount++;
if (collisionCount > (uint)entries.Length)
{
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
}
}
}
return false;
}
public bool Remove(TKey key, [MaybeNullWhen(false)] out TValue value)
{
// This overload is a copy of the overload Remove(TKey key) with one additional
// statement to copy the value for entry being removed into the output parameter.
// Code has been intentionally duplicated for performance reasons.
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (_buckets.Length > 0)
{
Debug.Assert(_entries.Length > 0, "entries should be non-empty");
uint collisionCount = 0;
var hashCode = (uint)(_comparer?.GetHashCode(key) ?? key.GetHashCode());
ref var bucket = ref GetBucket(hashCode);
var entries = _entries;
var last = -1;
var i = bucket - 1; // Value in buckets is 1-based
while (i >= 0)
{
ref var entry = ref entries[i];
if (entry._hashCode == hashCode && (_comparer?.Equals(entry._key, key) ?? EqualityComparer<TKey>.Default.Equals(entry._key, key)))
{
if (last < 0)
{
bucket = entry._next + 1; // Value in buckets is 1-based
}
else
{
entries[last]._next = entry._next;
}
value = entry._value;
Debug.Assert((StartOfFreeList - _freeList) < 0, "shouldn't underflow because max hashtable length is MaxPrimeArrayLength = 0x7FEFFFFD(2146435069) _freelist underflow threshold 2147483646");
entry._next = StartOfFreeList - _freeList;
#if NETCOREAPP
if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>())
#endif
{
entry._key = default!;
}
#if NETCOREAPP
if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>())
#endif
{
entry._value = default!;
}
_freeList = i;
_freeCount++;
return true;
}
last = i;
i = entry._next;
collisionCount++;
if (collisionCount > (uint)entries.Length)
{
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
}
}
}
value = default;
return false;
}
#pragma warning disable CS8767 // Nullability of reference types in type of parameter doesn't match implicitly implemented member (possibly because of nullability attributes).
public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
#pragma warning restore CS8767 // Nullability of reference types in type of parameter doesn't match implicitly implemented member (possibly because of nullability attributes).
{
ref var valRef = ref FindValue(key);
if (!RoslynUnsafe.IsNullRef(ref valRef))
{
value = valRef;
return true;
}
value = default;
return false;
}
public bool TryAdd(TKey key, TValue value)
=> TryInsert(key, value, InsertionBehavior.None);
bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly => false;
void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
=> CopyTo(array, index);
void ICollection.CopyTo(Array array, int index)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (array.Rank != 1)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
}
if (array.GetLowerBound(0) != 0)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
}
if ((uint)index > (uint)array.Length)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (array.Length - index < Count)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
}
if (array is KeyValuePair<TKey, TValue>[] pairs)
{
CopyTo(pairs, index);
}
else if (array is DictionaryEntry[] dictEntryArray)
{
var entries = _entries;
for (var i = 0; i < _count; i++)
{
if (entries[i]._next >= -1)
{
dictEntryArray[index++] = new DictionaryEntry(entries[i]._key, entries[i]._value);
}
}
}
else
{
var objects = array as object[];
if (objects == null)
{
ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
}
try
{
var count = _count;
var entries = _entries;
for (var i = 0; i < count; i++)
{
if (entries[i]._next >= -1)
{
objects[index++] = new KeyValuePair<TKey, TValue>(entries[i]._key, entries[i]._value);
}
}
}
catch (ArrayTypeMismatchException)
{
ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
}
}
}
IEnumerator IEnumerable.GetEnumerator()
=> new Enumerator(this, Enumerator.KeyValuePair);
/// <summary>
/// Ensures that the dictionary can hold up to 'capacity' entries without any further expansion of its backing storage
/// </summary>
public int EnsureCapacity(int capacity)
{
if (capacity < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
}
var currentCapacity = _entries.Length;
if (currentCapacity >= capacity)
{
return currentCapacity;
}
_version++;
if (_buckets.Length == 0)
{
return Initialize(capacity);
}
var newSize = HashHelpers.GetPrime(capacity);
Resize(newSize);
return newSize;
}
/// <summary>
/// Sets the capacity of this dictionary to what it would be if it had been originally initialized with all its entries
/// </summary>
/// <remarks>
/// This method can be used to minimize the memory overhead
/// once it is known that no new elements will be added.
///
/// To allocate minimum size storage array, execute the following statements:
///
/// dictionary.Clear();
/// dictionary.TrimExcess();
/// </remarks>
public void TrimExcess()
=> TrimExcess(Count);
/// <summary>
/// Sets the capacity of this dictionary to hold up 'capacity' entries without any further expansion of its backing storage
/// </summary>
/// <remarks>
/// This method can be used to minimize the memory overhead
/// once it is known that no new elements will be added.
/// </remarks>
public void TrimExcess(int capacity)
{
if (capacity < Count)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
}
var newSize = HashHelpers.GetPrime(capacity);
var oldEntries = _entries;
var currentCapacity = oldEntries.Length;
if (newSize >= currentCapacity)
{
return;
}
var oldCount = _count;
_version++;
Initialize(newSize);
var entries = _entries;
var count = 0;
for (var i = 0; i < oldCount; i++)
{
var hashCode = oldEntries[i]._hashCode; // At this point, we know we have entries.
if (oldEntries[i]._next >= -1)
{
ref var entry = ref entries[count];
entry = oldEntries[i];
ref var bucket = ref GetBucket(hashCode);
entry._next = bucket - 1; // Value in _buckets is 1-based
bucket = count + 1;
count++;
}
}
_count = count;
_freeCount = 0;
}
bool ICollection.IsSynchronized => false;
object ICollection.SyncRoot => this;
bool IDictionary.IsFixedSize => false;
bool IDictionary.IsReadOnly => false;
ICollection IDictionary.Keys => Keys;
ICollection IDictionary.Values => Values;
object? IDictionary.this[object key]
{
get
{
if (IsCompatibleKey(key))
{
ref var value = ref FindValue((TKey)key);
if (!RoslynUnsafe.IsNullRef(ref value))
{
return value;
}
}
return null;
}
set
{
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value);
try
{
var tempKey = (TKey)key;
try
{
this[tempKey] = (TValue)value!;
}
catch (InvalidCastException)
{
ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
}
}
catch (InvalidCastException)
{
ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey));
}
}
}
private static bool IsCompatibleKey(object key)
{
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
return key is TKey;
}
void IDictionary.Add(object key, object? value)
{
if (key == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value);
try
{
var tempKey = (TKey)key;
try
{
Add(tempKey, (TValue)value!);
}
catch (InvalidCastException)
{
ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue));
}
}
catch (InvalidCastException)
{
ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey));
}
}
bool IDictionary.Contains(object key)
{
if (IsCompatibleKey(key))
{
return ContainsKey((TKey)key);
}
return false;
}
IDictionaryEnumerator IDictionary.GetEnumerator()
=> new Enumerator(this, Enumerator.DictEntry);
void IDictionary.Remove(object key)
{
if (IsCompatibleKey(key))
{
Remove((TKey)key);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private ref int GetBucket(uint hashCode)
{
var buckets = _buckets;
return ref buckets[(int)HashHelpers.FastMod(hashCode, (uint)buckets.Length, _fastModMultiplier)];
}
private struct Entry
{
public uint _hashCode;
/// <summary>
/// 0-based index of next entry in chain: -1 means end of chain
/// also encodes whether this entry _itself_ is part of the free list by changing sign and subtracting 3,
/// so -2 means end of free list, -3 means index 0 but on free list, -4 means index 1 but on free list, etc.
/// </summary>
public int _next;
public TKey _key; // Key of entry
public TValue _value; // Value of entry
}
public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>, IDictionaryEnumerator
{
private readonly SegmentedDictionary<TKey, TValue> _dictionary;
private readonly int _version;
private int _index;
private KeyValuePair<TKey, TValue> _current;
private readonly int _getEnumeratorRetType; // What should Enumerator.Current return?
internal const int DictEntry = 1;
internal const int KeyValuePair = 2;
internal Enumerator(SegmentedDictionary<TKey, TValue> dictionary, int getEnumeratorRetType)
{
_dictionary = dictionary;
_version = dictionary._version;
_index = 0;
_getEnumeratorRetType = getEnumeratorRetType;
_current = default;
}
public bool MoveNext()
{
if (_version != _dictionary._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
// Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends.
// dictionary.count+1 could be negative if dictionary.count is int.MaxValue
while ((uint)_index < (uint)_dictionary._count)
{
ref var entry = ref _dictionary._entries[_index++];
if (entry._next >= -1)
{
_current = new KeyValuePair<TKey, TValue>(entry._key, entry._value);
return true;
}
}
_index = _dictionary._count + 1;
_current = default;
return false;
}
public KeyValuePair<TKey, TValue> Current => _current;
public void Dispose()
{
}
object? IEnumerator.Current
{
get
{
if (_index == 0 || (_index == _dictionary._count + 1))
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
if (_getEnumeratorRetType == DictEntry)
{
return new DictionaryEntry(_current.Key, _current.Value);
}
return new KeyValuePair<TKey, TValue>(_current.Key, _current.Value);
}
}
void IEnumerator.Reset()
{
if (_version != _dictionary._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
_index = 0;
_current = default;
}
DictionaryEntry IDictionaryEnumerator.Entry
{
get
{
if (_index == 0 || (_index == _dictionary._count + 1))
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
return new DictionaryEntry(_current.Key, _current.Value);
}
}
object IDictionaryEnumerator.Key
{
get
{
if (_index == 0 || (_index == _dictionary._count + 1))
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
return _current.Key;
}
}
object? IDictionaryEnumerator.Value
{
get
{
if (_index == 0 || (_index == _dictionary._count + 1))
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
return _current.Value;
}
}
}
[DebuggerTypeProxy(typeof(DictionaryKeyCollectionDebugView<,>))]
[DebuggerDisplay("Count = {Count}")]
public sealed class KeyCollection : ICollection<TKey>, ICollection, IReadOnlyCollection<TKey>
{
private readonly SegmentedDictionary<TKey, TValue> _dictionary;
public KeyCollection(SegmentedDictionary<TKey, TValue> dictionary)
{
if (dictionary == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
}
_dictionary = dictionary;
}
public Enumerator GetEnumerator()
=> new Enumerator(_dictionary);
public void CopyTo(TKey[] array, int index)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (index < 0 || index > array.Length)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (array.Length - index < _dictionary.Count)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
}
var count = _dictionary._count;
var entries = _dictionary._entries;
for (var i = 0; i < count; i++)
{
if (entries[i]._next >= -1)
array[index++] = entries[i]._key;
}
}
public int Count => _dictionary.Count;
bool ICollection<TKey>.IsReadOnly => true;
void ICollection<TKey>.Add(TKey item)
=> ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
void ICollection<TKey>.Clear()
=> ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
bool ICollection<TKey>.Contains(TKey item)
=> _dictionary.ContainsKey(item);
bool ICollection<TKey>.Remove(TKey item)
{
ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
return false;
}
IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator()
=> new Enumerator(_dictionary);
IEnumerator IEnumerable.GetEnumerator()
=> new Enumerator(_dictionary);
void ICollection.CopyTo(Array array, int index)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (array.Rank != 1)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
}
if (array.GetLowerBound(0) != 0)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
}
if ((uint)index > (uint)array.Length)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (array.Length - index < _dictionary.Count)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
}
if (array is TKey[] keys)
{
CopyTo(keys, index);
}
else
{
var objects = array as object[];
if (objects == null)
{
ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
}
var count = _dictionary._count;
var entries = _dictionary._entries;
try
{
for (var i = 0; i < count; i++)
{
if (entries[i]._next >= -1)
objects[index++] = entries[i]._key;
}
}
catch (ArrayTypeMismatchException)
{
ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
}
}
}
bool ICollection.IsSynchronized => false;
object ICollection.SyncRoot => ((ICollection)_dictionary).SyncRoot;
public struct Enumerator : IEnumerator<TKey>, IEnumerator
{
private readonly SegmentedDictionary<TKey, TValue> _dictionary;
private int _index;
private readonly int _version;
private TKey? _currentKey;
internal Enumerator(SegmentedDictionary<TKey, TValue> dictionary)
{
_dictionary = dictionary;
_version = dictionary._version;
_index = 0;
_currentKey = default;
}
public void Dispose()
{
}
public bool MoveNext()
{
if (_version != _dictionary._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
while ((uint)_index < (uint)_dictionary._count)
{
ref var entry = ref _dictionary._entries[_index++];
if (entry._next >= -1)
{
_currentKey = entry._key;
return true;
}
}
_index = _dictionary._count + 1;
_currentKey = default;
return false;
}
public TKey Current => _currentKey!;
object? IEnumerator.Current
{
get
{
if (_index == 0 || (_index == _dictionary._count + 1))
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
return _currentKey;
}
}
void IEnumerator.Reset()
{
if (_version != _dictionary._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
_index = 0;
_currentKey = default;
}
}
}
[DebuggerTypeProxy(typeof(DictionaryValueCollectionDebugView<,>))]
[DebuggerDisplay("Count = {Count}")]
public sealed class ValueCollection : ICollection<TValue>, ICollection, IReadOnlyCollection<TValue>
{
private readonly SegmentedDictionary<TKey, TValue> _dictionary;
public ValueCollection(SegmentedDictionary<TKey, TValue> dictionary)
{
if (dictionary == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
}
_dictionary = dictionary;
}
public Enumerator GetEnumerator()
=> new Enumerator(_dictionary);
public void CopyTo(TValue[] array, int index)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if ((uint)index > array.Length)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (array.Length - index < _dictionary.Count)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
}
var count = _dictionary._count;
var entries = _dictionary._entries;
for (var i = 0; i < count; i++)
{
if (entries[i]._next >= -1)
array[index++] = entries[i]._value;
}
}
public int Count => _dictionary.Count;
bool ICollection<TValue>.IsReadOnly => true;
void ICollection<TValue>.Add(TValue item)
=> ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
bool ICollection<TValue>.Remove(TValue item)
{
ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
return false;
}
void ICollection<TValue>.Clear()
=> ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet);
bool ICollection<TValue>.Contains(TValue item)
=> _dictionary.ContainsValue(item);
IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator()
=> new Enumerator(_dictionary);
IEnumerator IEnumerable.GetEnumerator()
=> new Enumerator(_dictionary);
void ICollection.CopyTo(Array array, int index)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (array.Rank != 1)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
}
if (array.GetLowerBound(0) != 0)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
}
if ((uint)index > (uint)array.Length)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (array.Length - index < _dictionary.Count)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
}
if (array is TValue[] values)
{
CopyTo(values, index);
}
else
{
var objects = array as object[];
if (objects == null)
{
ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
}
var count = _dictionary._count;
var entries = _dictionary._entries;
try
{
for (var i = 0; i < count; i++)
{
if (entries[i]._next >= -1)
objects[index++] = entries[i]._value!;
}
}
catch (ArrayTypeMismatchException)
{
ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType();
}
}
}
bool ICollection.IsSynchronized => false;
object ICollection.SyncRoot => ((ICollection)_dictionary).SyncRoot;
public struct Enumerator : IEnumerator<TValue>, IEnumerator
{
private readonly SegmentedDictionary<TKey, TValue> _dictionary;
private int _index;
private readonly int _version;
private TValue? _currentValue;
internal Enumerator(SegmentedDictionary<TKey, TValue> dictionary)
{
_dictionary = dictionary;
_version = dictionary._version;
_index = 0;
_currentValue = default;
}
public void Dispose()
{
}
public bool MoveNext()
{
if (_version != _dictionary._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
while ((uint)_index < (uint)_dictionary._count)
{
ref var entry = ref _dictionary._entries[_index++];
if (entry._next >= -1)
{
_currentValue = entry._value;
return true;
}
}
_index = _dictionary._count + 1;
_currentValue = default;
return false;
}
public TValue Current => _currentValue!;
object? IEnumerator.Current
{
get
{
if (_index == 0 || (_index == _dictionary._count + 1))
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
return _currentValue;
}
}
void IEnumerator.Reset()
{
if (_version != _dictionary._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
_index = 0;
_currentValue = default;
}
}
}
}
}
|